package 算法.分治法;

import java.util.Arrays;
import java.util.Scanner;

public class BinarySearch {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入数组的长度:");
        int i = scanner.nextInt();
        System.out.println("请输入数组的每一个元素（从小到大排列）:");
        int[] a=new int[i];
        for (int j =0; j <i ; j++) {
            a[j]=scanner.nextInt();
        }

        System.out.println("请输入要查找的值");
        int key=scanner.nextInt();
        int index = binarySearch(a, key);
        if (index==-1){
            System.out.println("没有找到此元素");
        }else{
            System.out.println("目标值在数组中第"+index+"位");
        }

    }
    /**
     * 二分查找的源代码
     * @param nums 数组
     * @param key 目标值
     * @return
     */
    public static int binarySearch(int[] nums, int key) {
        int l=0;int h=nums.length-1;
        while (l <= h){
//            int mid = (l + h) / 2;可能有加法的溢出问题
            int mid = l + (h - l) / 2;// h - l 不会出现加法溢出问题
            if (nums[mid] == key){
                return mid;
            }else if (nums[mid] > key){
                h = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return -1;
    }

}
